// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-26 20:52
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.GraphyTrain;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class HasPathSum {
    // DFS求树的路径和
    List<Integer> pathSum = new ArrayList<>();

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }
        DFS(root.right, root.val);
        DFS(root.left, root.val);
        for (Integer ps : pathSum) {
            if (ps == targetSum) {
                return true;
            }
        }
        return false;
    }

    private void DFS(TreeNode root, int sum) {
        // 使用树的深度遍历获取树的路径和
        if (root == null) {
            return;
        }
        sum += root.val;
        if (root.left == null && root.right == null) {
            // 到达路径结尾
            pathSum.add(sum);
        }
        if (root.left != null) {
            DFS(root.left, sum);
        }
        if (root.right != null) {
            DFS(root.right, sum);
        }
    }


}
